%\documentclass{article}
\documentclass{article}
\usepackage{xeCJK} 
\usepackage{geometry}
\usepackage{amsmath,amssymb}
\usepackage{splitbib}
\usepackage{seqsplit}
\usepackage{autoaligne}
\usepackage{aligned-overset}
\usepackage{fontspec}
\usepackage{tikz}
\usepackage{fancybox}
%\usepackage[UTF8]{ctex}
\geometry{left=1.5cm,right=1.5cm,top=1.5cm,bottom=1.5cm}
\begin{document}
\begin{titlepage}

\title{第一次作业}
%\author{战哲-32217050}
\date{\today}
\maketitle
\end{titlepage}
\setlength\parindent{2em}
\centerline{\Huge4.4-6}\vspace{1cm}\par

Argue that the solution to the recurrence $T(n)=T(n/3)+T(2n/3)+cn $ ,where c is a constant, is $\Omega(nlogn)$ by appealing to a recursion tree\par

\begin{flushleft}
  题解：
  \ovalbox{
\begin{tikzpicture}[level/.style={sibling distance=60mm/#1}]
\node [circle,draw] (z){$T(n)$}%这个是根节点
  child {node [circle,draw] (a) {${T(\frac{n}{3})}$}%根节点的左子节点
    child {node [circle,draw] (b) {$T(\frac{n}{9})$}%根节点的左子节点的左子节点
      child {node {$\vdots$}%这里代表的是省略号
        child {node [circle,draw] (d) {$T(1)$}}%这是最左边叶子节点
        child {node [circle,draw] (e) {$T(1)$}}%这里是从左往右数第二个叶子节点
      } 
      child {node {$\vdots$}}%这里代表省略号
    }
    child {node [circle,draw] (g) {$T(\frac{2n}{9})$}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
    }
  }
  child {node [circle,draw] (j) {${T(\frac{2n}{3})}$}%这里代表根节点的右子节点
    child {node [circle,draw] (k) {$T(\frac{2n}{9})$}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
    }
    child {node [circle,draw] (l) {$T(\frac{4n}{9})$}%这里代表第二行最后一个节点
      child {node {$\vdots$}}
      child {node (c){$\vdots$}
        child {node [circle,draw] (o) {$T(1)$}}
        child {node [circle,draw] (p) {$T(1)$}%到这里其实就停止了树的绘画
          child [grow=right] {node (q) {} edge from parent[draw=none]%这里是画的最右下子节点的右边的等号
            child [grow=right] {node (q) {$O_{k = \log_3 n}(n)=O(Cn)=O(n)$} edge from parent[draw=none]%等号右边的公式
              child [grow=up] {node (r) {$\vdots$} edge from parent[draw=none]%下面四行是从下到上介绍每行的时间复杂度的和
                child [grow=up] {node (s) {$C(\frac{n}{9}+\frac{2n}{9}+\frac{2n}{9}+\frac{4n}{9})=Cn$} edge from parent[draw=none]
                  child [grow=up] {node (t) {$C(\frac{n}{3}+\frac{2n}{3})=Cn$} edge from parent[draw=none]
                    child [grow=up] {node (u) {$Cn$} edge from parent[draw=none]}
                }
              }
            }
            child [grow=down] {node (v) {$O(n \cdot \lg n)$}edge from parent[draw=none]}
          }
        }
      }
    }
  }
};
\path (a) -- (j) node [midway] {+};
\path (b) -- (g) node [midway] {+};
\path (k) -- (l) node [midway] {+};
\path (k) -- (g) node [midway] {+};
\path (d) -- (e) node [midway] {+};
\path (o) -- (p) node [midway] {+};
\path (o) -- (e) node (x) [midway] {$\cdots$}
  child [grow=down] {%这里是最后一行的公式
    node (y) {$O\left(\displaystyle\sum_{i = 0}^k Cn\right)$}
    edge from parent[draw=none]
  };
\path (q) -- (r) node [midway] {+};
\path (s) -- (r) node [midway] {+};
\path (s) -- (t) node [midway] {+};
\path (s) -- (l) node [midway] {=};
\path (t) -- (u) node [midway] {+};
\path (z) -- (u) node [midway] {=};
\path (j) -- (t) node [midway] {=};
\path (y) -- (x) node [midway] {$\Downarrow$};
\path (v) -- (y) node (w) [midway] {$O\left(\displaystyle\sum_{i = 0}^k n\right)=O(k \cdot n)=O(log_3 n \cdot n)$};
\path (q) -- (v) node [midway] {=};
\path (e) -- (x) node [midway] {+};
\path (o) -- (x) node [midway] {+};
\path (y) -- (w) node [midway] {$=$};
\path (v) -- (w) node [midway] {$\Leftrightarrow$};
\path (r) -- (c) node [midway] {$\cdots$};
\end{tikzpicture}}
\end{flushleft}
注：这里可能会有叶子节点不在同一层数结束的情况，但是其实只差一个常数，对最后时间复杂度的分析不影响，所以就不在图中展示这一情况。
\newpage
\centerline{\Huge4.5-1}\vspace{1cm}\par
Use the master method to give tight asymptotic bounds for the following recurrences.\\\
\begin{align}
  \nonumber \textbf{a.} T(n)&=2T(n/4)+1 \\
  \nonumber \textbf{b.} T(n)&=2T(n/4)+\sqrt{n} \\
  \nonumber \textbf{c.} T(n)&=2T(n/4)+n \\
  \nonumber \textbf{d.} T(n)&=2T(n/4)+n^{2}
\end{align}
题解：\vspace{0.5cm}



\begin{flushleft}
  \textbf{a:}
%a: T(n)=2T(n/4)+1 $\implies$ a=2,b=1 $log_b a =log_4 2=\frac{1}{2}$\\\
\begin{align}
  \nonumber \because(n)=2T(n/4)+1 &\implies a=2,b=4 \\
  \nonumber &\implies log_b a =log_4 2=\frac{1}{2} \\
  \nonumber &\implies O(f(n))=O(n^{log_b a -\epsilon})(\epsilon=\dfrac{1}{2})\\
  \nonumber &\implies T(n)=\Theta(n^\dfrac{1}{2})
\end{align}

\textbf{b:}
\begin{align}
  \nonumber \because(n)=2T(n/4)+\sqrt{n} &\implies a=2,b=4 \\
  \nonumber &\implies log_b a =log_4 2=\frac{1}{2} \\
  \nonumber &\implies O(f(n))=\Theta(\sqrt{n})=\Theta(n^{log_b a})\\
  \nonumber &\implies T(n)=\Theta(\sqrt{n}\cdot lgn)
\end{align}

\textbf{c:}
\begin{align}
  \nonumber \because T(n)=2T(n/4)+\sqrt{n} &\implies a=2,b=4 \\
  \nonumber &\implies log_b a =log_4 2=\frac{1}{2} \\
  \nonumber &\implies \Omega(f(n))=\Omega(n^{log_b a}+\epsilon)(\epsilon=\dfrac{1}{2})\\
  %\nonumber &\implies T(n)=\Theta(\sqrt{n}\cdot lgn)\\
  \nonumber \because af(n/b)=2f(\dfrac{1}{4}n)&=\dfrac{1}{2}n,cf(n)=cn\\
  \nonumber \because we \ need \ to \ find \ a \ c \ with \ &constraint \ which \ is \ af(n/b) \leq cf(n)\\
  \nonumber \therefore let \ \dfrac{1}{2}\leq c <1 & \implies T(n)=\Omega(f(n))=\Theta(n)
\end{align}
\textbf{d:}
\begin{align}
  \nonumber \because T(n)=2T(n/4)+n^2 &\implies a=2,b=4 \\
  \nonumber &\implies log_b a =log_4 2=\frac{1}{2} \\
  \nonumber &\implies \Omega(f(n))=\Omega(n^{log_b a}+\epsilon)(\epsilon=\dfrac{3}{2})\\
  \nonumber \because we \ need \ to \ find \ a \ c \ with \ &constraint \ which \ is \ af(n/b) \leq cf(n)\\
  \nonumber \because af(n/b)=2f(\dfrac{1}{4}n)&=\dfrac{1}{8}n^2,cf(n)=cn^2\\
  \nonumber \therefore let \ \dfrac{1}{8}\leq c <1 & \implies T(n)=\Omega(f(n))=\Theta(n^2)
\end{align}
\end{flushleft}

  
\end{document}